flashcardfandomcom-20200213-history
Introductory Graph Theory
This page exists to contain flashcards for the following book: Introductory Graph Theory by Gary Chartrand Chapter 1 - Mathematical Models 1.1 Nonmathematical Models 1. Give three examples of models you have encountered. Indicate some pertinent features of each model and describe a feature each model lacks which would be useful for it to possess.||1) 2. Give an example of a model which is (a) larger than, (b) approximately the same size as the thing it represents.||(a) Those 3D/2D models you see in science classes of really small things, like atoms and bugs and neurons. (b)A fake skeleton, fake brain.|| 3. Explain the relationship that radio, television, motion pictures, and the theater have with models. What are some of the pertinent differences in how these media model?||Hmm...well, those media USE models when creating their media: weathermen on the radio or TV use mathematical models to predict the weather, and then they use 2D geographical models (maps) to show people what the weather will look like. 4. List some occupations which deal directly with nonmathematical models.||Fashion (actual people-models), teachers (3D plastic models of various phenomena), hobbyists (making model airplanes, model cars), policemen (if they have a map on their wall to show the location of crimes).|| 1.2 Mathematical Models 5. Why is the mathematical model described in Example 1.1 likely to be unsatisfactory? 6. What question would you like the mathematical model of Example 1.2 to answer? 7. You take a quart of milk whose temperature is 40° and you place it on the kitchen counter. The temperature in the kitchen is 75°. After 1 hour, the temperature of the milk has risen to 45°. What mathematical model would represent this situation? 8. In your opinion, what would be a better mathematical model than the given model for the situation described in Example 1.3? Why is yours preferable? 9. Imagine yourself in the position of the college senior of Example 1.4. List the alternatives you would choose and the factors that are important to you in making a decision. What do you think of this method of making decisions? 10. Give an example of a decision you are likely to make in the near future. Proceed as in Example 1.4 by listing alternatives, indicating important criteria, and assigning points. 11. What is the most important question a mathematical model for Example 1.5 should answer? 12. The following problem is rather common in a beginning calculus course. A square piece of cardboard, 12 centimeters on a side, is to have squares (all of the same size) cut out of its corners. Then its sides will be folded upward to produce a box with no top. What kind of mathematical model would represent this situation? What question would you like the mathematical model to answer? 13. Suppose you have a fair coin; that is, it is equally likely for heads or tails to appear if the coin is flipped. You are approached by a compulsive gambler who states that if you flip this coin four times and heads and tails appear twice each, then he will pay you $11. On the other hand, if you fail, you will pay him only $10. What kind of mathematical model would you identify with this situation? What question would you like the mathematical model to answer? 14. You must pay $10 to play the following game at a carnival. You flip a fair coin three times. When heads comes up the first time, you receive $5. If heads comes up a second time, you receive an additional $7. If heads occurs a third time, you receive yet another $9. Hence, it is possible to receive as much as $5 + $7 + $9 = $21 (for a net profit of $11) or as little as nothing (for a net loss of $10). What kind of mathematical model would you identify with this situation? What question should your model answer for you? 1.3 Graphs 15. Draw the graph with vertex set $$\mathit{V} = \left \{ u_{1}, u_{2}, u_{3}, u_{4}, u_{5} \right \}/$$ and edge set $$\mathit{V} = \left \{ u_{1}, u_{2}, u_{3}, u_{4}, u_{5} \right \}/$$. What is the corresponding irreflexive symmetric relation R on V? 16. Draw a graph G with vertex set $$\mathit{V} = \left \{ u_{1}, u_{2}, u_{3}, u_{4}, u_{5} \right \}/$$ and edge set E such that |E| is as large as possible. Determine E. 17. If a graph G has order 3, what are the possible sizes for G? 18. What is the maximum possible size of a graph of (a) order 3; (b) order 4; © order 5; (d) order n, where n is a positive integer? 19. Does an example exist of a graph of order 3 such that every two vertices are adjacent and every two edges are adjacent? Does such a graph of order 4 exist? 20. Is there a graph G of order five or more such that every vertex of G is incident with at least one edge, but no two edges are adjacent? 21. Let n >= 2 be an integer. If G is a graph of order n, what is the minimum size possible for G (in terms of n) if G contains a vertex which is adjacent to all other vertices of G? 22. Give an example of a graph G of positive size with the property that every vertex is incident with every edge. 23. Give an example of a graph exhibiting the properties that: (a) every vertex is adjacent to two vertices; and (b) every edge is adjacent with two edges. 24. If G is a nonempty set, why does it follow that the empty subset of G x G is an irreflexive, symmetric relation on G? Is the relation also transitive? 1.4 Graphs as Mathematical Models 25. In the graph of Example 1.6, what observation could you expect to make concerning the vertex associated with the "most popular child" in the class? What would you expect to find concerning a vertex associated with a new child in the class? Is it possible that a graph constructed at the beginning of the school year might be different from one constructed at the end of the school year? How could this happen? *26. Suppose we associate a graph G'' with a college class in the following manner. The vertices of ''G correspond to the students in the class, while two vertices of G'' are adjacent if and only if they correspond to two students having the same major. Can you describe the appearance of ''G? 27. In Example 1.7, it might be important for two platoons to communicate (indirectly, if not directly). How is it possible to determine by looking at the graph of Example 1.7 whether every two platoons can communicate with each other? 28. What would be an important question to ask concerning the situation described in Example 1.8? Could this question be answered with the aid of the corresponding graph? 29. The Student Council in a certain high school consists of 15 members. Ten different committees in school are made up of Student Council members. Some committees may have only a few members, while others may have many. Some Student Council members may below to no committees, and other members may below to several. Give examples of two graphs which describe this situation. Can you think of conditions which may make one graph more useful than the other? *30. We can generalize Exercise 29 in the following way. Let U be a finite nonempty set, and let S1, S2, ..., Sn be a collection of nonempty subsets of ''U. ''Find two examples of graphs which describe this situation. 31. Give an example of a real-life situation which can be represented by a graph. Draw the graph as it may appear. 1.5 Directed Graphs as Mathematical Models 1.6 Networks as Mathematical Models Chapter 2 - Elementary Concepts of Graph Theory Write the second section of your page here. Chapter 3 - Transportation Problems Write the first section of your page here. Chapter 4 - Connection Problems Write the second section of your page here. Chapter 5 - Party Problems Write the first section of your page here. Chapter 6 - Games and Puzzles Write the second section of your page here. Chapter 7 - Digraphs and Mathematical Models Write the first section of your page here. Chapter 8 - Graphs and Social Psychology Write the second section of your page here. Chapter 9 - Planar Graphs and Coloring Problems Write the first section of your page here. Chapter 10 - Graphs and Other Mathematics Write the second section of your page here. A.1 - Sets and Subsets Write the first section of your page here. A.2 - Cartesian Products and Relations Write the second section of your page here. A.3 - Equivalence Relations Write the first section of your page here. A.4 - Functions Write the second section of your page here. A.5 - Theorems and Proofs Write the first section of your page here. A.6 - Mathematical Induction Write the second section of your page here.